<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    查找 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						查找
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/20 17:53 下午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本概念</h2>
<ul>
<li>查找表：由同一类型的数据元素（或记录）构成的<strong>集合</strong></li>
<li>查找：查询（Searching）特定元素是否在表中</li>
<li>查找成功：若表中存在特定元素，称查找成功，应输出该记录</li>
<li>查找不成功：否则，称查找不成功（也应输出失败标志或失败位置）</li>
<li>静态查找：只查找，不改变集合内的数据元素</li>
<li>动态查找：查找，并改变（增删）集合内的数据元素</li>
<li>关键字：记录中某个数据项的值，可用来识别一个记录</li>
<li>主关键字：可以唯一标识一个记录的关键字</li>
<li>次关键字：识别若干记录的关键字</li>
</ul>
<p>查找的过程就是将给定的K值域文件中个记录的关键字项进行比较的过程，所以用比较次数的平均值来评估算法的优劣，称为平均查找长度（ASL，Average search length）</p>
<p><img src="media/16477699876627/16477844832491.jpg" alt="" /></p>
<ul>
<li>n：文件记录个数</li>
<li>P<sub>i</sub>：查找第i个记录的查找概率（通常取等概率，即P<sub>i</sub> = 1 / n）</li>
<li>C<sub>i</sub>：找到第i个记录时所经历的比较次数</li>
</ul>
<h2><a id="%E9%9D%99%E6%80%81%E6%9F%A5%E6%89%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>静态查找表</h2>
<h3><a id="%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE%EF%BC%88%E7%BA%BF%E6%80%A7%E6%9F%A5%E6%89%BE%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序查找（线性查找）</h3>
<p>用逐一比较的方法顺序查找关键字，是最直接的方法</p>
<pre class="line-numbers"><code class="language-c">typedef struct
{
    // 表基址，0号单元留空，表容量为全部元素
    ElemType *elem;
    // 表长，即表中数据元素个数
    int length;
} SSTable;

int Search_Seq(SSTable ST, KeyType key)
{
    int i;
    ST.elem[0].key = key;
    //key为哨兵位，置于0号元素
    for(i = ST.length; ST.elem[i].key != key; i++)
        ;
    return i;
}
</code></pre>
<ul>
<li>从后向前查找，设立0号元素为“哨兵位”，当关键字与末地址（0号元素）匹配时，返回i = 0，即查找不成功</li>
</ul>
<h4><a id="asl%EF%BC%88%E5%B9%B3%E5%9D%87%E6%9F%A5%E6%89%BE%E9%95%BF%E5%BA%A6%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>ASL（平均查找长度）</h4>
<ul>
<li>使用该方法查找第n个元素所需的比较次数为n，时间效率为O(n)</li>
<li>只考虑查找成功：<strong>P<sub>i</sub> = 1 / n</strong>，<strong>ASL = (n + 1) / 2</strong></li>
<li>考虑查找不成功：查找不成功需要比较的次数为n + 1次，将查找成功与不成功的概率一半，<strong>P<sub>i</sub> = 1 / 2n</strong>，<strong>ASL = 3(n + 1) / 4</strong></li>
</ul>
<h4><a id="%E4%BC%98%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>优点</h4>
<p>算法简单，适用于顺序结构和链式结构</p>
<h4><a id="%E7%BC%BA%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>缺点</h4>
<p>ASL太长，时间效率太低</p>
<h3><a id="%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE%EF%BC%88%E4%BA%8C%E5%88%86%E6%88%96%E5%AF%B9%E5%88%86%E6%9F%A5%E6%89%BE%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>折半查找（二分或对分查找）</h3>
<p>在数据已排序，形成排序表的情况下可用，将关键字与正中央的元素进行比较，若关键字小，则将范围缩小至有半部分查找，再与有半部分正中央的元素比较，每次缩小一半的范围，直到查找成功或失败</p>
<pre class="line-numbers"><code class="language-c">typedef struct
{
    // 表基址，0号单元留空，表容量为全部元素
    ElemType *elem;
    // 表长，即表中数据元素个数
    int length;
} SSTable;

int Search_Bin(SSTable ST, KeyType Key)
{
    int low, high, mid;
    low = 1;
    high = ST.length;
    while (low &lt;= high)
    {
        mid = (low + high) / 2;
        if (key == ST.elem[mid].key)
            return mid;
        else if (key &lt; ST.elem[mid].key)
            high = mid - 1;
        else
            low = mid + 1
    }
    return 0;
}
</code></pre>
<ul>
<li>每次折半查找，当查找范围的上界 &lt;= 下界时停止查找，查找失败</li>
</ul>
<h4><a id="asl%EF%BC%88%E5%B9%B3%E5%9D%87%E6%9F%A5%E6%89%BE%E9%95%BF%E5%BA%A6%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>ASL（平均查找长度）</h4>
<ul>
<li>通过第m次比较可以查找成功的元素有2<sup>m-1</sup>个</li>
</ul>
<p>假设表中共有n = 2<sup>m-1</sup>个元素</p>
<ul>
<li>全部比较次数为</li>
</ul>
<p><img src="media/16477699876627/16477926423892.jpg" alt="" /></p>
<ul>
<li>平均每个数据的查找时间需要除以n</li>
</ul>
<p><img src="media/16477699876627/16477926761381.jpg" alt="" /></p>
<p>最终得出折半查找法的ASL为<strong>log<sub>2</sub>n</strong></p>
<h4><a id="%E4%BC%98%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>优点</h4>
<p>时间效率高于顺序查找</p>
<h4><a id="%E7%BC%BA%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>缺点</h4>
<ul>
<li>只适用于排序表</li>
<li>单链表结构的元素定位只能从头指针开始，无法实现折半查找</li>
</ul>
<h3><a id="%E5%88%86%E5%9D%97%E6%9F%A5%E6%89%BE%EF%BC%88%E7%B4%A2%E5%BC%95%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>分块查找（索引顺序查找）</h3>
<p>这是一种顺序查找的改进方法，先让数据分块有序，即分成若干子表，要求每个子表中的关键字都比后一块中的关键字小（内部未必有序）</p>
<p>然后将各子表中的最大关键字<strong>构成一个索引表</strong>，表中还要包含每个子表的起始地址（即头指针）</p>
<p>即<strong>块内无次序</strong>，<strong>块与块之间有次序</strong><br />
<img src="media/16477699876627/16477930375529.jpg" alt="" /></p>
<h4><a id="asl%EF%BC%88%E5%B9%B3%E5%9D%87%E6%9F%A5%E6%89%BE%E9%95%BF%E5%BA%A6%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>ASL（平均查找长度）</h4>
<p>分块查找分为两步</p>
<ul>
<li>在索引表中查找</li>
<li>在块中查找</li>
</ul>
<p>用顺序查找</p>
<ul>
<li>ASL = 1 / 2 (n / s + s) + 1</li>
</ul>
<p><img src="media/16477699876627/16477932417177.jpg" alt="" /></p>
<ul>
<li>b：索引表中共有b个元素，每个元素被查找的概率为1 / b</li>
<li>s：每块共有s个元素，每个元素被查找的概率为1 / s</li>
</ul>
<p>用折半查找</p>
<ul>
<li>ASL = log<sub>2</sub>(n / s + 1) + s / 2</li>
</ul>
<p><img src="media/16477699876627/16477932944606.jpg" alt="" /></p>
<ul>
<li>s：每块共有s个元素，每个元素被查找的概率为1 / s</li>
</ul>
<h2><a id="%E5%8A%A8%E6%80%81%E6%9F%A5%E6%89%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>动态查找表</h2>
<ul>
<li>特点：表结构在查找过程中动态生成</li>
<li>要求：对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录</li>
</ul>
<h3><a id="%E7%BB%8F%E5%85%B8%E7%9A%84%E5%8A%A8%E6%80%81%E8%A1%A8%E2%80%94%E2%80%94%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>经典的动态表——二叉树</h3>
<h4><a id="%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉排序树的定义</h4>
<p>二叉排序树可能是一颗空树，或是具有以下性质的非空二叉树</p>
<ul>
<li>左子树的所有结点均小于根的值</li>
<li>右子树的所有结点均大于根的值</li>
<li>左右子树分别为二叉排序树</li>
</ul>
<p><img src="media/16477699876627/16477958853077.jpg" alt="" /></p>
<h4><a id="%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E7%9A%84%E6%8F%92%E5%85%A5%E4%B8%8E%E5%88%A0%E9%99%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉排序树的插入与删除</h4>
<p>将数据元素构造成二叉排序树的优点：</p>
<ul>
<li>查找过程与折半查找相似，，查找效率高</li>
<li>中序遍历此二叉树，将会得到一个关键字的有序序列（即实现排序运算）</li>
<li>一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，而且插入或删除元素时只需要修改指针而不需要移动元素</li>
</ul>
<p>这种既查找又插入的过程称为动态查找</p>
<p>二叉排序树既有类似于折半查找的特性，又采用了链表存储，是动态查找表的一种适宜表示</p>
<h5><a id="%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>插入操作</h5>
<ul>
<li>将第一个元素作为根结点</li>
<li>第二个元素若大于根结点，放置在右支，小于根结点，放置在左支</li>
<li>下一个元素与根结点比较判断放置在左支或右支，然后与左支或右支的结点作比较，继续向下放置，循环此操作</li>
<li>若当前元素已存在二叉树中，查找成功返回，不再重复插入</li>
</ul>
<h5><a id="%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>删除操作</h5>
<p>对于二叉排序树，删除书上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性</p>
<p>删除一个结点(*p)可能存在三种情况：</p>
<ul>
<li>*p为叶子：直接删除该结点和双亲中指向该结点的指针</li>
<li>*p只有一颗子树：令*p的子树变为原*p的双亲的左子树或右子树即可</li>
<li>*p有两颗子树：
<ul>
<li>方法一：将其右支删除并挂载到其左支的最右端，然后将其左支挂载到原*p的双亲上</li>
<li>方法二：用其左支最右端的结点覆盖到*p上，将<strong>原最右端结点的左支</strong>连接到<strong>原最右端结点的双亲</strong>上，然后将其左支挂载到原*p的双亲上</li>
</ul>
</li>
</ul>
<p><img src="media/16477699876627/16477978122350.jpg" alt="" /></p>
<h4><a id="%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E7%9A%84%E6%9F%A5%E6%89%BE%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉排序树的查找分析</h4>
<ul>
<li>二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径，比较的关键字次数 = 此节点的层次数，最多的比较次数 = 树的深度，即 <strong>log<sub>2</sub>n + 1</strong></li>
<li>一棵二叉排序树的平均查找长度为</li>
</ul>
<p><img src="media/16477699876627/16477987448395.jpg" alt="" /></p>
<p>最坏情况：</p>
<ul>
<li>即插入的n各元素从一开始就有序，变成单支树的形态，此时树的深度为n，ASL = (n + 1) / 2，此时查找效率与顺序查找相同</li>
</ul>
<p>最好情况：</p>
<ul>
<li>即与折半查找中的判定树相同（形态比较均衡），树的深度为<strong>log<sub>2</sub>n + 1</strong>，ASL = log<sub>2</sub>(n + 1) - 1，与折半查找相同</li>
</ul>
<p><img src="media/16477699876627/16477985495523.jpg" alt="" /></p>
<h4><a id="%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>平衡二叉树</h4>
<p>平衡二叉树又称AVL树，它是具有以下性质的二叉树：</p>
<ul>
<li>左右子树是平衡二叉树</li>
<li>所有结点的左右子树<strong>深度之差的绝对值小于等于1</strong>，即<code>| 左子树深度 - 右子树深度 | &lt;= 1</code></li>
</ul>
<p>为了方便起见，给每个结点附加一个数字，给出该结点<strong>左子树与右子树的高度差</strong>，这个数字称为结点的<strong>平衡因子（balance）</strong>，这样可以得到AVL的其它性质</p>
<p>任一结点的平衡因子只能取：<strong>-1、0或1</strong>，如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树失去了平衡，不再是AVL树</p>
<p>对于一棵有n个结点的AVL树，其高度保持在<strong>O(log<sub>2</sub>n)<strong>数量级，ASL也保持在</strong>O(log<sub>2</sub>n)</strong> 量级<br />
<img src="media/16477699876627/16477992426513.jpg" alt="" /></p>
<p>如果在一棵AVL树中插入一个新结点，可能造成失衡，此时必须调整树的结构，使之恢复平衡，我们成调整平衡的过程为<strong>平衡旋转</strong></p>
<p>平衡旋转可以归纳为四类：</p>
<ul>
<li>
<p>LL平衡旋转</p>
<ul>
<li>在其左支的左支插入新的结点</li>
<li><img src="media/16477699876627/16477999363535.jpg" alt="" /></li>
</ul>
</li>
<li>
<p>RR平衡旋转</p>
<ul>
<li>在其右支的右支插入新的结点</li>
<li><img src="media/16477699876627/16478001133667.jpg" alt="" /></li>
</ul>
</li>
<li>
<p>LR平衡旋转</p>
<ul>
<li>在其左支的右支插入新的结点</li>
<li><img src="media/16477699876627/16478003205248.jpg" alt="" /></li>
</ul>
</li>
<li>
<p>RL平衡旋转</p>
<ul>
<li>在其右支的左支插入新的结点</li>
<li><img src="media/16477699876627/16478005884678.jpg" alt="" /></li>
</ul>
</li>
</ul>
<h2><a id="%E5%93%88%E5%B8%8C%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>哈希表</h2>
<h3><a id="%E5%93%88%E5%B8%8C%E8%A1%A8%E7%9A%84%E6%A6%82%E5%BF%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>哈希表的概念</h3>
<ul>
<li>基本思想：建立<strong>关键码字</strong>与其<strong>存储位置</strong>的对应关系，或者说，由<strong>关键码的值决定数据的存储地址</strong></li>
<li>优点： 查找速度极快O(1)，查找效率与元素个数n无关
<ul>
<li>如：
<ul>
<li>将<code>2001011810201</code>的所有信息存入<code>V[01]</code>单元</li>
<li>将<code>2001011810202</code>的所有信息存入<code>V[02]</code>单元</li>
<li>......</li>
<li>将<code>2001011810231</code>的所有信息存入<code>V[31]</code>单元</li>
</ul>
</li>
<li>欲查找学号为<code>2001011810216</code>的信息，可以直接访问<code>V[16]</code>单元</li>
</ul>
</li>
<li>哈希方法（杂凑法）：选取某个函数，依照函数<strong>按关键字计算元素的存储位置</strong>，并按此存放，查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功</li>
<li>哈希函数（杂凑函数）：哈希方法中使用的<strong>转换函数</strong>称为哈希函数（杂凑函数）</li>
<li>哈希表（杂凑表）：按<strong>上述思想构造的表</strong>称为哈希表（杂凑表）</li>
<li>冲突：通常关键码的集合比哈希地址集合大得多，因此经过哈希函数变换后，<strong>可能将不同的关键码映射到同一个哈希地址上</strong>，这种现象称为<strong>冲突</strong></li>
</ul>
<h3><a id="%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0%E7%9A%84%E6%9E%84%E9%80%A0%E6%96%B9%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>哈希函数的构造方法</h3>
<h4><a id="%E7%9B%B4%E6%8E%A5%E5%AE%9A%E5%9D%80%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>直接定址法</h4>
<pre class="line-numbers"><code class="language-c">Hash(key) = a * key + b
// a、b为常数
</code></pre>
<p>优点：</p>
<ul>
<li>以关键码key的某个线性函数值为哈希地址，不会产生冲突</li>
</ul>
<p>缺点：</p>
<ul>
<li>需要占用连续的地址空间，空间效率低</li>
</ul>
<h4><a id="%E9%99%A4%E7%95%99%E4%BD%99%E6%95%B0%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>除留余数法</h4>
<pre class="line-numbers"><code class="language-c">Hash(key) = key % p
// p是一个整数
</code></pre>
<p>特点：</p>
<ul>
<li>以关键码除以p的余数作为哈希地址</li>
</ul>
<p>技巧：</p>
<ul>
<li>若设计的哈希表长为m，则一般取p &lt;= m且为质数（也可以是不包含小于2-质因子的合数）</li>
</ul>
<h4><a id="%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数字分析法</h4>
<h4><a id="%E5%B9%B3%E6%96%B9%E5%8F%96%E4%B8%AD%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>平方取中法</h4>
<h4><a id="%E6%8A%98%E5%8F%A0%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>折叠法</h4>
<h4><a id="%E9%9A%8F%E6%9C%BA%E6%95%B0%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>随机数法</h4>
<h3><a id="%E5%86%B2%E7%AA%81%E5%A4%84%E7%90%86%E6%96%B9%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>冲突处理方法</h3>
<h4><a id="%E5%BC%80%E6%94%BE%E5%AE%9A%E5%9D%80%E6%B3%95%EF%BC%88%E5%BC%80%E5%9C%B0%E5%9D%80%E6%B3%95%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>开放定址法（开地址法）</h4>
<p>设计思路：</p>
<ul>
<li>有冲突时就寻找下一个空的哈希地址，只要哈希表足够大，总能找到空的哈希地址，并将数据元素存入</li>
</ul>
<p>具体实现：</p>
<ul>
<li>线性探测法
<ul>
<li>假设x位出现冲突，则寻找<strong>x + 1位</strong>、<strong>x + 2位</strong>以此类推，直到找到一个空的哈希地址</li>
<li>容易占用后续数据元素本该占据的位置</li>
</ul>
</li>
<li>二次探测法
<ul>
<li>假设x位出现冲突，则寻找<strong>x + 增量序列</strong>，增量序列为<strong>1<sub>2</sub>、-1<sub>2</sub>、2<sub>2</sub>、-2<sub>2</sub></strong> 以此类推</li>
</ul>
</li>
<li>伪随机探测法</li>
</ul>
<h4><a id="%E9%93%BE%E5%9C%B0%E5%9D%80%E6%B3%95%EF%BC%88%E6%8B%89%E9%93%BE%E6%B3%95%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链地址法（拉链法）</h4>
<p>基本思想：</p>
<ul>
<li>将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构</li>
</ul>
<h4><a id="%E5%86%8D%E5%93%88%E5%B8%8C%E6%B3%95%EF%BC%88%E5%8F%8C%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0%E6%B3%95%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>再哈希法（双哈希函数法）</h4>
<p>采用多个哈希函数，当产生冲突时，计算另一个哈希函数，直到冲突不再发生<br />
优点：</p>
<ul>
<li>不易产生聚集</li>
</ul>
<p>缺点：</p>
<ul>
<li>增加了计算时间</li>
</ul>
<h4><a id="%E5%BB%BA%E7%AB%8B%E5%85%AC%E5%85%B1%E6%BA%A2%E5%87%BA%E5%8C%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>建立公共溢出区</h4>
<p>将不冲突的记录存入哈希表，所有关键字和基本表中关键字为同义词的的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表</p>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>